package company;

import java.util.*;

/** 127 单词接龙 超时了
 * 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
 * <p>
 * 每对相邻的单词之间仅有单个字母不同。
 * 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
 * sk == endWord
 * 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 * 输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
 * 解释：存在 2 种最短的转换序列：
 * "hit" -> "hot" -> "dot" -> "dog" -> "cog"
 * "hit" -> "hot" -> "lot" -> "log" -> "cog"
 * 示例 2：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
 * 输出：[]
 * 解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
 */
public class FindLadders127 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String beginWords = sc.nextLine();
        String endWords = sc.nextLine();
        String[] split = sc.nextLine().split(",");
        List<String> wordIdList = new ArrayList<>(Arrays.asList(split));
        List<List<String>> ladders = findLadders(beginWords, endWords, wordIdList);
    }


    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        // 定义队列
        Deque<List<String>> qu = new LinkedList();
        Set<String> wordId = new HashSet<>(wordList);
        List<List<String>> res = new ArrayList<>();
        if (!wordId.contains(endWord)) {
            return res;
        }
        wordId.remove(beginWord);

        // 队列访问
        List<String> path = new ArrayList<>();
        path.add(beginWord);
        qu.offer(path);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        // 每个单词需要经过转换
        while (!qu.isEmpty()) {
            int currentSize = qu.size();

            // 处理每一层
            for (int i = 0; i < currentSize; i++) {
                getSingelResult(endWord, qu, wordId, res, visited);
            }

            // 避免重复使用
            for (String s : visited) {
                wordId.remove(s);
            }
        }
        return res;
    }

    public static void getSingelResult(String endWord, Deque<List<String>> qu, Set<String> wordId, List<List<String>> res, Set<String> visited) {
        List<String> currentPath = qu.poll();
        String currentWord = currentPath.get(currentPath.size() - 1);
        char[] chars = currentWord.toCharArray();

        // 每个单词经历的转换次数
        for (int j = 0; j < endWord.length(); j++) {
            char tmp = chars[j];
            // 每次转换需要从a->z
            for (char k = 'a'; k <= 'z'; k++) {
                if (tmp == k) {
                    continue;
                }
                chars[j] = k;
                String newWord = String.valueOf(chars);
                if (wordId.contains(newWord)) {
                    List<String> newPath = new ArrayList<>(currentPath);
                    newPath.add(newWord);
                    visited.add(newWord);
                    if (!newWord.equals(endWord)) {
                        qu.add(newPath);
                    } else {
                        res.add(newPath);
                    }
                }
            }
            chars[j] = tmp;
        }
    }
}
